#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/29 15:33
# ===========================================
#       题目名称： 46. 全排列
#       题目地址： https://leetcode.cn/problems/permutations/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res_dict = dict()  # 返回值字典 k 已排序的值 v 未排序的值
        cur_carry, size = 0, len(nums)  # 当前位数 列表大小
        while cur_carry < size:
            if res_dict:
                temp_res_dict = dict()
                for k, v in res_dict.items():
                    for i in range(len(v)):
                        temp_v = v.copy()
                        del temp_v[i]
                        temp_res_dict[k + (v[i], )] = temp_v
                res_dict = temp_res_dict
            else:
                for i in range(size):
                    temp_nums = nums.copy()
                    cur_index = 0       # 排除和当前nums[i]相同的元素
                    while cur_index < len(temp_nums) and temp_nums:
                        if temp_nums[cur_index] == nums[i]:
                            del temp_nums[cur_index]
                        else:
                            cur_index += 1
                    res_dict[(nums[i],)] = temp_nums
            # print("cur_carry = %s, res_dict = %s" % (cur_carry, res_dict))
            cur_carry += 1

        return [list(item) for item in res_dict.keys()]


if __name__ == '__main__':
    s = Solution()
    # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    print(s.permute(nums=[1, 2, 3]))
    # [[0,1],[1,0]]
    print(s.permute(nums=[0, 1]))
    # [[1]]
    print(s.permute(nums=[1]))
